package l.l.w.practice.WordBreakII;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created by llw on 2017/10/15.
 */
public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> list = new ArrayList<String>();
        List<String> ret = new ArrayList<String>();
        rec(s, dict, list, ret);
        return ret;
    }

    public void rec(String s, Set<String> dict, List<String> list, List<String> ret) {
        if(!isBreak(s, dict)){  // test before run to avoid TLE
            return;
        }
        if(s.length() == 0) {
            String concat = "";
            for(int i=0; i<list.size(); i++) {
                concat += list.get(i);
                if(i != list.size()-1) {
                    concat += " ";
                }
            }
            ret.add(concat);
            return;
        }

        for(String cur : dict) {
            if(cur.length() > s.length()) {     // avoid out of boundary
                continue;
            }
            String substr = s.substring(0, cur.length());
            if(substr.equals(cur)) {
                list.add(substr);
                rec(s.substring(cur.length()), dict, list, ret);
                list.remove(list.size()-1);
            }
        }
    }

    public boolean isBreak(String s, Set<String> dict) {
        boolean[] canBreak = new boolean[s.length()+1];
        canBreak[0] = true;

        for(int i=1; i<=s.length(); i++) {
            boolean flag = false;
            for(int j=0; j<i; j++) {
                if(canBreak[j] && dict.contains(s.substring(j,i))) {
                    flag = true;
                    break;
                }
            }
            canBreak[i] = flag;
        }
        return canBreak[s.length()];
    }

    public static void main(String[] args) {
        String s= "catsanddog";
        HashSet<String> set = new HashSet<>();
        set.add("cat");
        set.add("cats");
        set.add("and");
        set.add("sand");
        set.add("dog");

        List<String> result = new Solution().wordBreak(s, set);
        System.out.println(result);
    }
}

